package com.leetcode.algorithm.y22.m06;

/**
 * 518. 零钱兑换 II
 * 
 * https://leetcode.cn/problems/coin-change-2/
 * 
 * @author jie.deng
 *
 */
class Question0518Solution02 {

	public int change(int amount, int[] coins) {
		if (amount == 0) {
			return 1;
		}
		int len = coins.length;
		// dp[i][j]表示使用前i种硬币凑成金额j的组合数
		int[][] dp = new int[len][amount + 1];
		dp[0][0] = 1;
		// 状态初始化
		for (int i = coins[0]; i <= amount; i += coins[0]) {
			dp[0][i] = 1;
		}

		// 状态转移方程
		for (int j = 1; j < coins.length; j++) {
			dp[j][0] = 1;
			for (int i = 1; i <= amount; i++) {
				if (i >= coins[j]) {
					dp[j][i] = dp[j][i - coins[j]] + dp[j - 1][i];
				} else {
					dp[j][i] = dp[j - 1][i];
				}
			}
		}

		return dp[len - 1][amount];
	}

}